The global Internet Protocol (IP) address space currently offers a theoretical maximum of 4,294,967,296 hosts (232). In reality, this address space has been allocated in fairly large contiguous blocks. Address allocation authorities distribute blocks of the IP address space to individual organizations interconnected through networks that make up the Internet as a whole.
These address blocks must be globally reachable according to routing information exchanged via routing protocols such as Border Gateway Protocol (BGP), Open Shortest Path First (OSPF), and Intermediate System to Intermediate System (IS-IS). Routing information, which is both used locally and exchanged with peers, generally refers to address blocks in terms of an IP address and a mask, called a Classless Inter-Domain Routing (CIDR) block. For example, an IP address block written 192.172.226/24 refers to all IP addresses having the same prefix for the first 24 bits (i.e. 192.172.226). This block starts at address 192.172.226.0 and contains 256 possible individual IP addresses (232-24). Routing tables associate this IP address block, which includes an address/mask pair, with a next hop IP address, and routers forward all traffic with a destination IP address in this block to the next hop listed in their local routing tables.
IP address assignment and other routing configuration functions are strongly related to each other. The fact that they are typically configured separately, however, tends to prevent them from being seen at the same time, leading to potential inconsistencies between intended and actual configurations.
Previous work has attempted to show how much of the IPv4 address space, i.e., 232 possible individual hosts, is in use in the global Internet core using BGP routing tables. This work generated a simple map of 16,777,216
      (                  2        32            256        )    ,possible clusters of 256 hosts with 24-bit CIDR blocks. This map of the global address space showed whether each address block was routable and whether it was allocated to some organization. A BGP routing table was used to determine whether address blocks were routable, and reverse Domain Name System (DNS) lookups were used to determine allocation. The BGP routing table used to generate the map was collected from a Route View server storing BGP routes from 15 peers spread throughout the Internet.
One of the roles of BGP is to minimize the number of IP address blocks advertised between peers by summarizing small blocks in larger blocks, thus causing a loss of granularity. When trying to retrieve the IP address space in use from BGP routing tables, one can only accurately assert which IP address blocks are not reachable. Information about small IP address blocks which may be allocated and routed in the network is thus lost. Furthermore, this methodology does not show IP addresses used by transport devices such as routers.
According to another technique called scanning, query probes such as ping packets are sent to each possible individual IP address. If a response to the query is received, then the IP address is assessed as in use. Scanning all of the IP addresses allocated in a network may be seen as the most accurate way to evaluate which ones are reachable. Still, this solution faces a number of problems, including a) scalability: scanning all possible IP addresses is a tremendous process which has to be repeated often in order to get an up-to-date image of the IP address space in use, b) security: hosts might be configured to not respond to query probes for security purposes and yet still be active to send and/or receive traffic, and c) filtering: probes might not be forwarded to protect the system from possible attacks. This scheme is therefore not entirely accurate.
A further conventional technique uses a Dynamic Host Configuration Protocol (DHCP) server to automate the assignment of IP addresses to each host in a system. This solution keeps track of the IP addresses assigned, and these addresses are assumed to be reachable. Although one might consider that keeping track of IP addresses automatically assigned by a DHCP server would allow an accurate assessment of which IP addresses are in use in the network, this assignment is not correlated with the actual configuration of equipment in the network. The assignment of an IP address to a host thus only reflects the intent to use this IP address, but does not guarantee its reachability, that is, whether it will actually be routed in a network. Such an IP address represents an inconsistency between the DHCP server and actual configuration, but is mistakenly considered allocated and thus reachable according to this solution.
The above techniques do not provide an accurate assessment of which blocks of the IP address space are reachable in a communication system, or provide for detection of potential routing configuration issues or errors such as inconsistencies between intended address assignments and actual configurations.
Therefore, there remains a need for apparatus and methods for validating routing configuration, such as to verify the reachability of electronic addresses in communication systems.